package exercises.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <a href="https://leetcode-cn.com/problems/permutations/">
 * 46. 全排列</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 * @author or2
 * @date 2021年10月13日 时间: 13:48
 */
public class No46 {
    public List<List<Integer>> permute(int[] nums) {
        var res = new ArrayList<List<Integer>>();
        var stack = new ArrayDeque<Integer>(nums.length);

        for (int i = 0, numsLength = nums.length; i < numsLength; i++)
            dfs(nums, i, stack, res);

        return res;
    }

    private void dfs(int[] nums, int curIndex, Deque<Integer> stack, List<List<Integer>> res) {
        stack.push(nums[curIndex]);

        if (stack.size() == nums.length) {
            res.add(new ArrayList<>(stack));
            stack.pop();
            return;
        }

        int num = nums[curIndex];
        nums[curIndex] = -11;

        for (int j = 0, numsLength = nums.length; j < numsLength; j++)
            if (nums[j] != -11)
                dfs(nums, j, stack, res);

        nums[curIndex] = num;
        stack.pop();
    }
}
